#include<iostream>
using namespace std;
const int N = 1e4 + 10;
int arr[205];
int map[N][N];
int dis[N];
bool flag[N];
int n, m;
void Dij(int x)
{
	memset(dis, 0x3f, sizeof(dis));
	dis[x] = 0;
	flag[x] = 1;
	for (int i = 1; i <= n; i++) {
		if (i != x) {
			dis[i] = min(dis[i], dis[x] + map[x][i]);
		}
	}
	while (1) {
		int mi = 0x3f3f3f3f, pos = -1;
		for (int i = 1; i <= x; i++) {
			if (!flag[i] && dis[i] < mi) {
				pos = i;
				mi = dis[i];
			}
		}
		if (pos == -1) {
			break;
		}
		for (int i = 1; i <= n; i++) {
			dis[i] = min(dis[i], map[pos][i] + dis[pos]);
		}
		flag[pos] = 1;
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		map[u][v] = w;
		map[v][u] = w;
	}
	Dij(1)
	return 0;
}